package leetcode.code600;

public class Solution1 extends Solution600 {
	@Override
	public int findIntegers(int n) {
		int len = Integer.toBinaryString(n).length();
		int[][] array = new int[31][4];

		array[1][0] = 2;
		array[1][1] = 0;
		array[1][2] = 1;
		array[1][3] = 2;// 这和这之前一共有几个

		array[2][0] = 1;
		array[2][1] = 2;
		array[2][2] = 3;
		array[2][3] = 3;// 这和这之前一共有几个
		for (int i = 3; i < len + 1; i++) {
			array[i][0] = array[i - 2][3];// 取决于i-2和i-2之前
			array[i][1] = (1 << (i - 1));
			array[i][2] = (1 << i) - 1;
			array[i][3] = array[i][0] + array[i - 1][3];
		}
		int sum = array[len - 1][3];
		int start = array[len][1];
		int end = array[len][2];
		while (start <= end && start <= n) {
			sum++;
			System.out.println(sum + " " + start + " " + Integer.toBinaryString(start));
			int temp = start;
			int count1 = 0;
			while (temp > 0) {
				if ((temp & 1) == 1) {
					count1++;
				} else if (count1 > 0) {
					count1--;
				}
				if (count1 == 2) {
					--sum;
					System.out.println(sum + " " + start + " " + Integer.toBinaryString(start));
					break;
				}
				temp >>>= 1;
			}
			start++;
		}
		return sum;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
//		so.debug1();
//		so.debug2();
//		so.debug3();
		int n = 1000000000;
		int r = so.findIntegers(n);
//		test(n);
		System.out.println("r " + r);
//		System.out.println(0 >> 1);
	}

	public static void test(int size) {
		size += 5;
		int col1 = String.valueOf(size).length() + 1;
		int col2 = Integer.toBinaryString(size).length() + 1;
		for (int i = 0; i < size; i++) {
			myPrint(i, col1, Integer.toBinaryString(i), col2);
		}
	}

	public static void myPrint(Object... objects) {
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < objects.length; i += 2) {
			sb.append(tail(String.valueOf(objects[i]), Integer.valueOf(String.valueOf(objects[i + 1]))));
		}
		System.out.println(sb.toString());
	}

	public static String tail(String s, int max) {
		int blank = max - s.length();
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < blank; i++) {
			sb.append(' ');
		}
		sb.append(s);
		return sb.toString();
	}

}
